package tree;

/**
 * @author way
 * @create 2025-02-12 17:14
 */
public class _106_buildTree {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) return null;
        // 调用递归方法构建树
        return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode build(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
        if (postorderStart == postorderEnd) return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++) {
            if (inorder[middleIndex] == rootVal) {
                break;
            }
        }

        root.left = build(inorder, inorderStart, middleIndex, postorder, postorderStart, postorderStart + (middleIndex - inorderStart));
        root.right = build(inorder, middleIndex + 1, inorderEnd, postorder, postorderStart + (middleIndex - inorderStart), postorderEnd - 1);
        return root;
    }
}
